題目

題目翻譯

給定 n 對的括號，撰寫一函式去生成所有合法的括號組合。

解題思路

問題描述:
給定一個整數 n，需要生成所有可能且有效的由 n 對括號組成的組合。

思路分析:

1. 回溯法：這道題可以用回溯法解決。在生成括號的過程中，我們同時追蹤左括號和右括號的使用情況，保證每次生成的括號序列都是合法的。
2. 約束條件：
   • 每當生成新的括號組合時，我們確保左括號 ( 的數量不超過 n。
   • 右括號 ) 的數量不能超過當前已經使用的左括號數量，這樣能保證括號序列合法。
3. 回溯步驟：
   • 先生成左括號，然後生成右括號。
   • 當生成的序列長度達到 2 * n 時，說明一個完整的合法括號組合已經生成，將其加入答案。

解題步驟

1. 初始化：

   • 定義一個回溯函數 combine，該函數會接收當前生成的字符串 nowString，以及已經使用的左括號數量 left 和右括號數量 right。
   • combine 函數會不斷遞歸生成新的括號組合，直到生成的序列達到長度 2 * n。

2. 遞歸結束條件：

   • 當 nowString 的長度等於 2 * n 時，將其加入結果集，並停止該遞歸路徑。

3. 左括號生成條件：

   • 當左括號的數量小於 n 時，可以添加一個左括號並繼續回溯。

4. 右括號生成條件：

   • 當右括號的數量小於左括號的數量時，可以添加一個右括號並繼續回溯。

5. 返回結果：

   • 回溯結束後，返回生成的所有括號組合。

code

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        // 開始回溯生成括號組合
        combine("", 0, 0, n);
        return ans;
    }
    
    // 回溯函數，用於生成括號組合
    void combine(string nowString, int left, int right, const int& max) {
        // 如果當前字符串長度等於 2 * n，則將其加入結果
        if (nowString.size() == max * 2) {
            ans.emplace_back(nowString);
            return;
        }
        
        // 當左括號數量小於 n 時，添加左括號
        if (left < max) {
            combine(nowString + "(", left + 1, right, max);
        }
        
        // 當右括號數量小於左括號數量時，添加右括號
        if (right < left) {
            combine(nowString + ")", left, right + 1, max);
        }
    }
    
private:
    vector<string> ans;  // 存儲結果的向量
};